//76.最小覆盖子串
class Solution {
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
         
        int[] hash1 = new int[128];//用数组模拟hash表，用来统计字符串t中字符的频次
        int[] hash2 = new int[128];//统计窗口中字符出现的频次
        
        int kinds = 0;//字符串t中，有多少种字符
        for(char ch : t){
            if(hash1[ch] == 0){
                kinds++;
            }
            hash1[ch]++;
        }

        int left = 0;
        int count = 0;//统计有效字符的种类
        int minlen = Integer.MAX_VALUE,begin = -1;
        for(int right = 0;right < s.length;right++){
            char in = s[right];
            //进窗口+维护count
            if(++hash2[in] == hash1[in]){
                count++;
            }
            //判断
            while(count == kinds){
                //更新结果
                if(right - left +1 < minlen){
                    begin = left;
                    minlen = right - left+1;
                }
                //出窗口+维护count
                char out = s[left++];
                if(hash2[out]-- == hash1[out]){
                    count--;
                }
            }  
        }
        if(begin == -1){
            return new String();
        }else{
            return ss.substring(begin,begin + minlen);
        }
    }
}